{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "class KMeansClassifier():\n",
    "    \"this is a k-means classifier\"\n",
    "    \n",
    "    \n",
    "    def __init__(self, k=3, initCent='random', max_iter=5000):\n",
    "        \"\"\"构造函数，初始化相关属性\"\"\"\n",
    "        self._k = k\n",
    "        self._initCent = initCent#初始中心\n",
    "        self._max_iter = max_iter#最大迭代\n",
    "        #一个m*2的二维矩阵，矩阵第一列存储样本点所属的族的索引值，\n",
    "        #第二列存储该点与所属族的质心的平方误差\n",
    "        self._clusterAssment = None#样本点聚类结结构矩阵\n",
    "        self._labels = None\n",
    "        self._sse = None#SSE（Sum of squared errors）平方误差和\n",
    "     \n",
    "        \n",
    "    def _calEDist(self, arrA, arrB):\n",
    "        \"\"\"\n",
    "        功能：欧拉距离距离计算\n",
    "        输入：两个一维数组\n",
    "        \"\"\"\n",
    "        arrA_temp = arrA.copy()\n",
    "        arrB_temp = arrB.copy()\n",
    "        arrA_temp[0] = arrA_temp[0]*0.16\n",
    "        arrA_temp[1] = arrA_temp[1]*0.005\n",
    "        arrB_temp[0] = arrB_temp[0]*0.16\n",
    "        arrB_temp[1] = arrB_temp[1]*0.005\n",
    "        return np.math.sqrt(sum(np.power(arrA_temp - arrB_temp, 2)))\n",
    "    \n",
    "    \n",
    "    def _calMDist(self, arrA, arrB):\n",
    "        \"\"\"\n",
    "        功能：曼哈顿距离距离计算\n",
    "        输入：两个一维数组\n",
    "        \"\"\"\n",
    "        return sum(np.abs(arrA-arrB))\n",
    "\n",
    "\n",
    "    def _randCent(self, data_X, k):\n",
    "        \"\"\"\n",
    "        功能：随机选取k个质心\n",
    "        输出：centroids #返回一个m*n的质心矩阵\n",
    "        \"\"\"\n",
    "        n = data_X.shape[1] - 3 #获取特征值的维数(要删除一个用于标记的id列和经纬度值)\n",
    "        centroids = np.empty((k,n))  #使用numpy生成一个k*n的矩阵，用于存储质心\n",
    "        for j in range(n):\n",
    "            minJ = min(data_X[:,j+1])\n",
    "            rangeJ = max(data_X[:,j+1] - minJ)\n",
    "            #使用flatten拉平嵌套列表(nested list)\n",
    "            centroids[:, j] = (minJ + rangeJ * np.random.rand(k, 1)).flatten()\n",
    "        return centroids \n",
    "    \n",
    "    \n",
    "    def fit(self, data_X):\n",
    "        \"\"\"\n",
    "        输入：一个m*n维的矩阵\n",
    "        \"\"\"\n",
    "        if not isinstance(data_X, np.ndarray) or \\\n",
    "               isinstance(data_X, np.matrixlib.defmatrix.matrix):\n",
    "            try:\n",
    "                data_X = np.asarray(data_X)\n",
    "            except:\n",
    "                raise TypeError(\"numpy.ndarray resuired for data_X\")\n",
    "                \n",
    "        m = data_X.shape[0]  #获取样本的个数\n",
    "        #一个m*2的二维矩阵，矩阵第一列存储样本点所属的族的编号，\n",
    "        #第二列存储该点与所属族的质心的平方误差\n",
    "        self._clusterAssment = np.zeros((m,2)) \n",
    "        \n",
    "        #创建k个点，作为起始质心\n",
    "        if self._initCent == 'random':\n",
    "            self._centroids = self._randCent(data_X, self._k)\n",
    "            \n",
    "        clusterChanged = True\n",
    "        #循环最大迭代次数\n",
    "        for _ in range(self._max_iter): #使用\"_\"主要是因为后面没有用到这个值\n",
    "            clusterChanged = False\n",
    "            for i in range(m):   #将每个样本点分配到离它最近的质心所属的族\n",
    "                minDist = np.inf #首先将minDist置为一个无穷大的数\n",
    "                minIndex = -1    #将最近质心的下标置为-1\n",
    "                for j in range(self._k): #次迭代用于寻找元素最近的质心\n",
    "                    arrA = self._centroids[j,:]\n",
    "                    arrB = data_X[i,1:4]\n",
    "                    distJI = self._calEDist(arrA, arrB) #计算距离\n",
    "                    if distJI < minDist:\n",
    "                        minDist = distJI\n",
    "                        minIndex = j\n",
    "                if self._clusterAssment[i, 0] != minIndex or self._clusterAssment[i, 1] > minDist**2:\n",
    "                    clusterChanged = True\n",
    "                    self._clusterAssment[i,:] = minIndex, minDist**2\n",
    "            if not clusterChanged:#若所有样本点所属的族都不改变,则已收敛,结束迭代\n",
    "                break\n",
    "            for i in range(self._k):#更新质心，将每个族中的点的均值作为质心\n",
    "                index_all = self._clusterAssment[:,0] #取出样本所属簇的编号\n",
    "                value = np.nonzero(index_all==i) #取出所有属于第i个簇的索引值\n",
    "                ptsInClust = data_X[value[0]]    #取出属于第i个簇的所有样本点\n",
    "                self._centroids[i,:] = np.mean(ptsInClust[:,1:4], axis=0) #计算均值,赋予新的质心\n",
    "        \n",
    "        self._labels = self._clusterAssment[:,0]\n",
    "        self._sse = sum(self._clusterAssment[:,1])\n",
    "    \n",
    "    \n",
    "    def predict(self, X):#根据聚类结果，预测新输入数据所属的族\n",
    "        #类型检查\n",
    "        if not isinstance(X,np.ndarray):\n",
    "            try:\n",
    "                X = np.asarray(X)\n",
    "            except:\n",
    "                raise TypeError(\"numpy.ndarray required for X\")\n",
    "        \n",
    "        m = X.shape[0]#m代表样本数量\n",
    "        preds = np.empty((m,))\n",
    "        for i in range(m):#将每个样本点分配到离它最近的质心所属的族\n",
    "            minDist = np.inf\n",
    "            for j in range(self._k):\n",
    "                distJI = self._calEDist(self._centroids[j,:], X[i,:])\n",
    "                if distJI < minDist:\n",
    "                    minDist = distJI\n",
    "                    preds[i] = j\n",
    "        return preds\n",
    "\n",
    "        \n",
    "class biKMeansClassifier():\n",
    "    \"this is a binary k-means classifier\"\n",
    "    \n",
    "    def __init__(self, k=3):\n",
    "        \n",
    "        self._k = k\n",
    "        self._centroids = None\n",
    "        self._clusterAssment = None\n",
    "        self._labels = None\n",
    "        self._sse = None\n",
    "        \n",
    "    \n",
    "    def _calEDist(self, arrA, arrB):\n",
    "        \"\"\"\n",
    "        功能：欧拉距离距离计算\n",
    "        输入：两个一维数组\n",
    "        \"\"\"\n",
    "        return np.math.sqrt(sum(np.power(arrA-arrB, 2)))\n",
    "        \n",
    "    def fit(self, X):\n",
    "        m = X.shape[0]\n",
    "        self._clusterAssment = np.zeros((m,2))\n",
    "        centroid0 = np.mean(X, axis=0).tolist()\n",
    "        centList =[centroid0]\n",
    "        for j in range(m):#计算每个样本点与质心之间初始的平方误差\n",
    "            self._clusterAssment[j,1] = self._calEDist(np.asarray(centroid0), \\\n",
    "                                        X[j,:])**2\n",
    "        \n",
    "        while (len(centList) < self._k):\n",
    "            lowestSSE = np.inf\n",
    "            #尝试划分每一族,选取使得误差最小的那个族进行划分\n",
    "            for i in range(len(centList)):\n",
    "                index_all = self._clusterAssment[:,0] #取出样本所属簇的索引值\n",
    "                value = np.nonzero(index_all==i) #取出所有属于第i个簇的索引值\n",
    "                ptsInCurrCluster = X[value[0],:] #取出属于第i个簇的所有样本点\n",
    "                clf = KMeansClassifier(k=2)\n",
    "                clf.fit(ptsInCurrCluster)\n",
    "                #划分该族后，所得到的质心、分配结果及误差矩阵\n",
    "                centroidMat, splitClustAss = clf._centroids, clf._clusterAssment\n",
    "                sseSplit = sum(splitClustAss[:,1])\n",
    "                index_all = self._clusterAssment[:,0] \n",
    "                value = np.nonzero(index_all==i)\n",
    "                sseNotSplit = sum(self._clusterAssment[value[0],1])\n",
    "                if (sseSplit + sseNotSplit) < lowestSSE:\n",
    "                    bestCentToSplit = i\n",
    "                    bestNewCents = centroidMat\n",
    "                    bestClustAss = splitClustAss.copy()\n",
    "                    lowestSSE = sseSplit + sseNotSplit\n",
    "            #该族被划分成两个子族后,其中一个子族的索引变为原族的索引\n",
    "            #另一个子族的索引变为len(centList),然后存入centList\n",
    "            bestClustAss[np.nonzero(bestClustAss[:,0]==1)[0],0]=len(centList)\n",
    "            bestClustAss[np.nonzero(bestClustAss[:,0]==0)[0],0]=bestCentToSplit\n",
    "            centList[bestCentToSplit] = bestNewCents[0,:].tolist()\n",
    "            centList.append(bestNewCents[1,:].tolist())\n",
    "            self._clusterAssment[np.nonzero(self._clusterAssment[:,0] == \\\n",
    "                                        bestCentToSplit)[0],:]= bestClustAss \n",
    "                   \n",
    "        self._labels = self._clusterAssment[:,0] \n",
    "        self._sse = sum(self._clusterAssment[:,1])\n",
    "        self._centroids = np.asarray(centList)\n",
    "                                \n",
    "    def predict(self, X):#根据聚类结果，预测新输入数据所属的族\n",
    "        #类型检查\n",
    "        if not isinstance(X,np.ndarray):\n",
    "            try:\n",
    "                X = np.asarray(X)\n",
    "            except:\n",
    "                raise TypeError(\"numpy.ndarray required for X\")\n",
    "        \n",
    "        m = X.shape[0]#m代表样本数量\n",
    "        preds = np.empty((m,))\n",
    "        for i in range(m):#将每个样本点分配到离它最近的质心所属的族\n",
    "            minDist = np.inf\n",
    "            for j in range(self._k):\n",
    "                distJI = self._calEDist(self._centroids[j,:],X[i,:])\n",
    "                if distJI < minDist:\n",
    "                    minDist = distJI\n",
    "                    preds[i] = j\n",
    "        return preds\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
